package com.kevin.Code.BinarySearch;

/**
 * @author Vinlee Xiao
 * @Classname FindFirstLastPosition
 * @Description Leetcode 34 剑指Offer53 剑指Offer专项57 三刷
 * @Date 2022/2/24 11:23
 * @Version 1.0
 */
public class FindFirstLastPosition {

    /**
     * 方法一:更加简单相比 Leetcode 34
     *
     * @param nums
     * @param target
     * @return
     */
    public int search1(int[] nums, int target) {
        int lastNum = binarySearchByRightNum(nums, target, 0, nums.length - 1);
        int firstNum = binarySearchByRightNum(nums, target - 1, 0, nums.length - 1);
        return lastNum - firstNum;
    }

    /**
     * @param nums
     * @param target
     * @return
     */
    public int search2(int[] nums, int target) {
        int firstNum = binarySearchByLeftNum(nums, target, 0, nums.length - 1);
        int lastNum = binarySearchByLeftNum(nums, target + 1, 0, nums.length - 1);
        return lastNum - firstNum;
    }

    /**
     * @param nums
     * @param low
     * @param high
     * @return
     */
    public int binarySearchByRightNum(int[] nums, int target, int low, int high) {
        while (low <= high) {
            int mid = (low + high) >> 1;
            if (nums[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return high;
    }

    /**
     * @param nums
     * @param target
     * @param low
     * @param high
     * @return
     */
    public int binarySearchByLeftNum(int[] nums, int target, int low, int high) {
        while (low <= high) {
            int mid = (low + high) >> 1;
            if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return low;
    }

    /**
     * 查找target在数组中的位置
     *
     * @param nums
     * @param target
     * @param low
     * @param high
     * @return
     */
    public int binarySearch(int[] nums, int target, int low, int high) {
        while (low <= high) {
            int mid = (low + high) >> 1;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return -1;
    }

    /**
     * 在排序数组中查找元素的第一个和最后一个位置
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        int leftIndex = binarySearchByNumber(nums, target, 0, nums.length - 1, true);
        int rightIndex = binarySearchByNumber(nums, target, 0, nums.length - 1, false);

        if (leftIndex < 0 || leftIndex > nums.length - 1 || nums[leftIndex] != target) {
            leftIndex = -1;
        }

        if (rightIndex < 0 || rightIndex > nums.length - 1 || nums[rightIndex] != target) {
            rightIndex = -1;
        }

        return new int[]{leftIndex, rightIndex};
    }

    /**
     * @param nums
     * @param target
     * @param low
     * @param high
     * @param flag
     * @return
     */
    public int binarySearchByNumber(int[] nums, int target, int low, int high, boolean flag) {
        while (low <= high) {
            //求平均值
            int mid = (low + high) >> 1;
            if (target < nums[mid] || (flag && target <= nums[mid])) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return flag ? low : high;
    }


    public static void main(String[] args) {
        int[] nums = new int[]{5, 7, 7, 8, 8, 10};
        int target = 7;
        FindFirstLastPosition findFirstLastPosition = new FindFirstLastPosition();
        int[] pos = findFirstLastPosition.searchRange(nums, target);
        System.out.println(pos[0]);
        System.out.println(pos[1]);
//
//        System.out.println(pos[1]);
//        int i = findFirstLastPosition.search(nums, target);
//        System.out.println(i);
//        int i = findFirstLastPosition.binarySearchByLeftNum(nums, target, 0, nums.length - 1);
//        System.out.println(i);

//
    }
}
